class MyLinkedList
{
public:
    MyLinkedList()
    {
        this->head = DoubleLinkedListNode();
        this->tail = DoubleLinkedListNode();
        this->head.next = &this->tail;
        this->tail.previous = &this->head;
        this->_size = 0;
    }

    int get(int index)
    {
        DoubleLinkedListNode *pos = this->locateIndex(index);
        if (pos == nullptr)
        {
            return -1;
        }
        else
        {
            return pos->val;
        }
    }

    void addAtHead(int val)
    {
        auto newNode = new DoubleLinkedListNode(val, &this->head, this->head.next);
        this->head.next->previous = newNode;
        this->head.next = newNode;
        ++this->_size;
    }

    void addAtTail(int val)
    {
        auto newNode = new DoubleLinkedListNode(val, this->tail.previous, &this->tail);
        this->tail.previous->next = newNode;
        this->tail.previous = newNode;
        ++this->_size;
    }

    void addAtIndex(int index, int val)
    {
        if (index <= 0)
        {
            this->addAtHead(val);
            return;
        }
        else if (index == this->_size)
        {
            this->addAtTail(val);
            return;
        }
        else if (index > this->_size)
        {
            return;
        }
        DoubleLinkedListNode *pos = this->locateIndex(index);
        auto newNode = new DoubleLinkedListNode(val, pos->previous, pos);
        pos->previous->next = newNode;
        pos->previous = newNode;
        ++this->_size;
    }

    void deleteAtIndex(int index)
    {
        DoubleLinkedListNode *pos = this->locateIndex(index);
        if (pos == nullptr)
        {
            return;
        }
        pos->previous->next = pos->next;
        pos->next->previous = pos->previous;
        delete pos;
        --this->_size;
    }

    class DoubleLinkedListNode
    {
    public:
        int val;
        DoubleLinkedListNode *previous;
        DoubleLinkedListNode *next;
        DoubleLinkedListNode() : val(0), previous(nullptr), next(nullptr) {}
        DoubleLinkedListNode(int val) : val(val), previous(nullptr), next(nullptr) {}
        DoubleLinkedListNode(int val, DoubleLinkedListNode *previous, DoubleLinkedListNode *next) : val(val), previous(previous), next(next) {}
    };

private:
    DoubleLinkedListNode head;
    DoubleLinkedListNode tail;
    int _size;

    DoubleLinkedListNode *locateIndex(int index)
    {
        DoubleLinkedListNode *pos = nullptr;
        if (index < 0 || index >= this->_size)
        {
            return pos;
        }
        if (index <= this->_size - 1 - index)
        {
            pos = this->head.next;
            int i = index;
            while (i)
            {
                pos = pos->next;
                --i;
            }
        }
        else
        {
            pos = this->tail.previous;
            int i = this->_size - 1 - index;
            while (i)
            {
                pos = pos->previous;
                --i;
            }
        }
        return pos;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */